package pack1;


import java.util.ArrayList;
import java.util.HashSet;

public class CutApple {

    public static void main(String[] args) {
        CutApple ca = new CutApple();
        int[][] apples = {{1,1},{2,3},{3,3},{4,3},{1,4}};
        System.out.println(ca.minCut(apples));
    }

    int minCut(int[][] input){
        HashSet<String> apples = new HashSet<>();
        for (int[] locs: input) {
            apples.add(locs[0]+"_"+locs[1]);
        }
        int cut = 0;
        while (!apples.isEmpty()){ //n
            //记录最多的可切水果
            ArrayList<String> canCut = new ArrayList<>();
            for (String s1: apples) {  //n
                ArrayList<String> cutLR = new ArrayList<>(); //横切
                ArrayList<String> cutUD = new ArrayList<>(); //竖切
                ArrayList<String> cutLD = new ArrayList<>(); //↘切
                ArrayList<String> cutRD = new ArrayList<>(); //↙切
                String[] s1xy = s1.split("_");
                int s1x = Integer.parseInt(s1xy[0]), s1y = Integer.parseInt(s1xy[1]);
                for (String s2:apples) {  //n
                    String[] s2xy = s2.split("_");
                    int s2x = Integer.parseInt(s2xy[0]), s2y = Integer.parseInt(s2xy[1]);
                    if(s1x==s2x) cutLR.add(s2);
                    if(s1y==s2y) cutUD.add(s2);
                    if((s1x-s2x)==(s1y-s2y)) cutLD.add(s2);
                    if((s1x-s2x)==(s2y-s1y)) cutRD.add(s2);
                }
                canCut = canCut.size()>cutLR.size()?canCut:cutLR;
                canCut = canCut.size()>cutUD.size()?canCut:cutUD;
                canCut = canCut.size()>cutLD.size()?canCut:cutLD;
                canCut = canCut.size()>cutRD.size()?canCut:cutRD;
            }
            //从apples里删除
            for (String apple: canCut) {
                apples.remove(apple);
            }
            //记一刀
            cut++;
        }
        return cut;
    }
}
